Cầu được khởi công xây dựng vào năm 2014 và dự kiến hoàn thành, thông xe vào cuối năm 2019, tuy nhiên ngày thông xe cầu được dời đến tháng 3 năm 2020. Cây cầu được xây dựng bởi công ty Daelim của Hàn Quốc[6] và Tổng Công ty Xây dựng Quốc gia Trung Quốc (CSCEC).[7] Dự án được báo cáo trị giá 1,6 tỷ đô la Brunei (tương đương 1,2 tỷ đô la Mỹ tính đến tháng 3 năm 2018).[8]

Việc xây dựng cầu được chia thành sáu "gói" hoặc hợp đồng.[9] Đầu tiên là CC1 hay gọi là Đường hầm Mentiri, là một loạt các đường hầm xuyên qua Mentiri Ridges nối Jalan Utama Mentiri với Jalan Kota Batu là đường hai chiều có kiểm soát. Các gói thầu xây dựng khác bao gồm CC2, CC3 và CC4 lần lượt bao gồm Cầu biển, Cầu dẫn đường và Cầu cạn Temburong. Việc xây của CC2 và CC3 được trao cho Daelim, một công ty của Hàn Quốc, chịu trách nhiệm xây dựng hệ thống cầu cạn và hai cây cầu dây văng bắc qua vịnh Brunei.[6] Trong khi đó, Cơ quan Xây dựng Quốc gia Trung Quốc nhận hợp đồng CC4 chịu trách nhiệm xây dựng cầu cạn xuyên qua đầm lầy ngập mặn của Khu bảo tồn Rừng Labu[10]. CC5A và CC5B lần lượt là hệ thống điều khiển lưu lượng và hệ thống cấp điện, và hệ thống cung cấp điện.[11]

Do đại dịch COVID-19, cây cầu đã được khánh thành sớm hơn so với kế hoạch vào ngày 17 tháng 3 năm 2020, một ngày sau khi Brunei cấm hầu hết người nước ngoài không cư trú vào đất nước và hầu hết công dân và cư dân rời đi để tránh tình trạng quận Temburong bị ngăn cách hoàn toàn với phần còn lại của đất nước.[2]

Vào ngày 14 tháng 7 năm 2020, nhân dịp sinh nhật lần thứ 74 của Quốc vương Haji Hassanal Bolkiah, cây cầu được đặt tên là cầu Sultan Haji Omar Ali Saifuddien để vinh danh người cha quá cố của ông, cựu Quốc vương Haji Omar Ali Saifuddien III, người được xem là kiến trúc sư của Brunei hiện đại.[12]